package dfs;

public class 累加树 {

    public boolean isAdditiveNumber(String num) {
        int len = num.length();
        if (len<3)
            return false;
        //确认前两个数
        long first=0, second=0;
        for (int i = 0; i < len-2; i++) {
            //开头第一个数不能为0
            if (i!=0 && first==0)
                return false;
            first=first*10+(num.charAt(i)-'0');
            //进行下次循环的时候，将second 初始化为0
            second=0;
            for (int j = i+1; j < len-1; j++) {
                if (j!=i+1 && second==0)
                    break;
                second=second*10+(num.charAt(j)-'0');
                if (dfs(num,len,j+1,first,second))
                    return true;
            }
        }
        return false;
    }
    private boolean dfs(String num, int len, int index, long first, long second) {
        //index是下一个数字的索引
        if (index>=len)
            return true;
        long tem=0;
        long sum=first+second;
        for (int i = index; i < len; i++) {
            if (i!=index && tem==0)
                return false;
            tem=tem*10+(num.charAt(i)-'0');
            if (dfs(num,len,i+1,second,tem) && tem==sum)
                return true;
        }
        return false;
    }
}
